<?php

class dijkstra{

	public $route_reversed = array(); //routen falsche reihenfolge
	
	public $output; //contains the output-array

	public $q; //list of all stops

		function dijkstra($startNode,$endNode){

		$this->init($startNode); //fülle $q und setze startknoten distanz = 0
		
		 $u; //current Node
		//while q isnt empty
		while(strcmp($u->uri,$endNode)!=0 ){ //$endNode is the URI of a node
			$tempDist = 9999; //initialvaule "infinity"
			foreach ($this->q as $shortestDistanceNode){	//alle Knoten?
				if($shortestDistanceNode->weight < $tempDist){ //wenn die Distanz zum beliebigen knoten 
				// kleiner als die aktuelle distanz ist, aber es ist nicht unbedingt das Maximum oder
				// Minimum... es wird lediglich benötigt, dass es < ist
				// initial der Startknoten mit 0;
					$tempDist = $shortestDistanceNode->weight; //overwrite the current shortest distance
					$u = $shortestDistanceNode; //$u is now the node with the shortest distance
				}
			}
			
			//remove the found node from the list with all nodes
			unset($this->q[$u->uri]);
			
			//get all neighbors
			$u->successor = $this->get_neighbor($u->uri); //set the successor of u to its direct neighbor
			//for each neighbor
			foreach ($u->successor as $successor){ 
				//if the successor of u is in q
				if($this->q[$successor] != null){ 
					$this->distance_update($u,$this->q[$successor]); //update the distance to the current neighbor
				}
			}
			
		}
		//traverse the predecessors of u	
		$this->getRoute($u);
		//reverse this array
		$this->output=array_reverse($this->route_reversed);
		//return
		return $this->output;

	}
	
	/*
	 * this function gets the predecessor of the node $u and writes the label, 
	 * the routeId and the location in an array
	 */
	function getRoute($u){
		array_push($this->route_reversed,array(
			'route' => $u->routeId,
			'label' => $u->label, 
			'lat' => $u->lat,
			'lon' => $u->lon
			));
		foreach ($u->predecessor as $pre){
			$this->getRoute($pre);
		}
	
	}
	/*
	 * this function querys the repository for the neighbors of a node
	 * which is identified by its uri
	 */
	function get_neighbor($uri){
		$out = array();
		//new query with Stops within 0.001° lat and long
		$queryNeighbour = '
		select distinct ?neighbourStops ?routeId where {
			{
				?stop a transit:Stop. 
				?serviceStopsStart transit:stop ?stop;
				transit:sequence ?seq;
				transit:service ?service. 
				?serviceStopsStart2 transit:service ?service.
				?serviceStopsFromServiceStopsStart transit:service ?service;
				transit:sequence ?seq2;
				transit:stop ?neighbourStops.

				?service transit:route ?route.
				?route ns3:routeId ?routeId.

			Filter(sameTerm(?stop, <'.$uri.'>) && (?seq2-?seq)=1) 
			} UNION {
					select distinct (?nstop as ?neighbourStops) ?routeId where {
					?stop a transit:Stop.
					?service transit:stop ?stop;
					ns4:lat ?lat;
					ns4:long ?long.

					?nstop a transit:Stop;
					ns4:lat ?nlat;
					ns4:long ?nlong.
					?nserviceStop transit:stop ?nstop.
					?nservice transit:serviceStop ?nserviceStop;
					transit:route ?route.
					?route ns3:routeId ?routeId.

					Filter (sameTerm(?stop, <'.$uri.'>) && (abs(?nlat-?lat) < 0.001) && (abs(?nlong-?long) < 0.001) && !sameTerm(?nstop, <'.$uri.'>))
				}
			}
		}
		';
		//execute the query
		$query_result = query($queryNeighbour);
		//decode the result which is in a json notation
		$json = json_decode(strval($query_result), true);
        $jsonresults = $json['results'];
        $jsonbindings = $jsonresults['bindings'];
		//iterate over the results
        for ($y = 0; $y < count($jsonbindings);$y++) {;			
			$out[$y] = $jsonbindings[$y]['neighbourStops']['value']; //set the neighbors
			//the following line is incomprehensible except for dennis
			$this->q[$jsonbindings[$y]['neighbourStops']['value']]->routeId = $jsonbindings[$y]['routeId']['value'];
		}
		return $out;
	}
	
	/*
	 * this function updates the distance of a node
	 */
	function distance_update($actual,$v){
			$alternativ = $actual->weight + 1;
			if($alternativ < $v->weight){
				$v->weight = $alternativ;
				$v->predecessor[$actual->uri] = $actual;				
			}
	}
	
	/*
	 * this function initializes the list containing all nodes
	 */
	function init($startNode){
			//execute a query which gets all stops
			$rawStops = query('select ?stop ?uri ?lat ?long where { ?stop a transit:Stop. ?stop ns4:lat ?lat. ?stop ns4:long ?long. ?stop rdfs:label ?uri. } ');
			//decode the result
			$json = json_decode(strval($rawStops), true);
			$jsonresults = $json['results'];
			$jsonbindings = $jsonresults['bindings'];
			
			// fill the list containing all nodes (q)
			for ($y = 0; $y < count($jsonbindings);$y++) {
				$this->q[utf8_decode($jsonbindings[$y]['stop']['value'])] = new Stop(9999, //q[URI] -> Stop
										utf8_decode($jsonbindings[$y]['lat']['value']),
										utf8_decode($jsonbindings[$y]['long']['value']),
										utf8_decode($jsonbindings[$y]['stop']['value']),
										utf8_decode($jsonbindings[$y]['uri']['value']), //uri = label...
										"", // empty predecessor
										""); //empty successor
			}
			$this->q[$startNode]->weight=0;						
	}

}

/*
 * this function can be called to compute the shortest path between a supplied start and a destination
 */
function startDijkstra($start, $end){
	$rawStart = query('select *  where {?stop a transit:Stop;rdfs:label "'.$start.'"^^rdf:string;}');
	$jsonStart = json_decode(strval($rawStart), true);
	$jsonresults = $jsonStart['results']['bindings'][0]['stop']['value'];
		
	$rawEnd= query('select *  where {?stop a transit:Stop;rdfs:label "'.$end.'"^^rdf:string;}');
	$jsonEnd = json_decode(strval($rawEnd), true);
	$jsonresultsEnd = $jsonEnd['results']['bindings'][0]['stop']['value'];

	$route = new dijkstra($jsonresults,$jsonresultsEnd);
	
	return $route->output;	
}

/**
 * Class Stop.
 */
class Stop{
	
	var $weight;
	var $lat;
	var $lon;
	var $uri;
	var $label;
	var $predecessor;
	var $successor;
	var $routeId;
	
	function Stop($weight, $lat, $lon, $uri, $label, $predecessor, $successor){
		$this->weight = $weight;
		$this->lat = $lat;
		$this->lon = $lon;
		$this->uri = $uri;
		$this->label = $label;
		$this->predecessor = $predecessor;
		$this->successor = $successor;
	}
	
}
?>
